//
// Created by fh on 2021/6/25.
//

#include "Heap.h"

/* 创建初始化顺序堆 */
SqHeap * SqHeapCreateAndInit(int isBigTopHeap) {
    SqHeap *sqHeap = (SqHeap *) malloc(sizeof(SqHeap));
    sqHeap->index = 0;
    sqHeap->isBigTopHeap = isBigTopHeap;
    return sqHeap;
}

/* 顺序堆插入 */
Status SqHeapInsert(SqHeap *sqHeap,int value) {
    if (!sqHeap) {
        return ERROR;
    }
    if (sqHeap->index >= MAXSIZE-1) {
        /* 没有空间了 */
        return ERROR;
    }

    // 先插入
    ++sqHeap->index;
    sqHeap->data[sqHeap->index] = value;
    // 再堆化
    int currentIndex = sqHeap->index;
    int fatherIndex = sqHeap->index / 2;
    while (fatherIndex != 0) {
        if (sqHeap->isBigTopHeap == 1) {
            // 大顶堆
            if (sqHeap->data[fatherIndex] < sqHeap->data[currentIndex]) {
                int tmp = sqHeap->data[fatherIndex];
                sqHeap->data[fatherIndex] = sqHeap->data[currentIndex];
                sqHeap->data[currentIndex] = tmp;
            }
        } else {
            // 小顶堆
            if (sqHeap->data[fatherIndex] > sqHeap->data[currentIndex]) {
                int tmp = sqHeap->data[fatherIndex];
                sqHeap->data[fatherIndex] = sqHeap->data[currentIndex];
                sqHeap->data[currentIndex] = tmp;
            }
        }
        currentIndex = fatherIndex;
        fatherIndex = currentIndex / 2;
    }
    return OK;
}

/* 顺序堆删除 */
Status SqHeapDelete(SqHeap *sqHeap,int value) {
    // 先查找
    if (sqHeap->index < 1) {
        return ERROR;
    }
    if (sqHeap->isBigTopHeap == 1) {
        // 大顶堆
        if (value > sqHeap->data[1]) {
            // 没找到
            printf("没找到\n");
            return ERROR;
        }
    } else {
        // 小顶堆
        if (value < sqHeap->data[1]) {
            // 没找到
            printf("没找到\n");
            return ERROR;
        }
    }

    int findIndex = -1;
    for (int i = 1; i <= sqHeap->index; ++i) {
        if (value == sqHeap->data[i]) {
            findIndex = i;
            break;
        }
    }
    if (findIndex != -1) {
        int deleteValue = sqHeap->data[findIndex]; // 也就是参数value
        int lastValue = sqHeap->data[sqHeap->index];
        sqHeap->index--;
        sqHeap->data[findIndex] = lastValue;

        int curIndex = findIndex;
        int fatherIndex = findIndex / 2;
        int leftIndex = curIndex * 2;
        int rightIndex = curIndex * 2 + 1;

        int heapCondition = deleteValue > lastValue;
        if (sqHeap->isBigTopHeap == 1) {
            // 大顶堆
            heapCondition = deleteValue > lastValue;
        } else {
            // 小顶堆
            heapCondition = deleteValue < lastValue;
        }
        if (heapCondition) {
            // 需要从上往下堆化
            while (1) {
                if (leftIndex > sqHeap->index) {
                    // 没有子树了
                    break;
                } else if (rightIndex > sqHeap->index) {
                    // 只有左子树
                    int cur = sqHeap->data[curIndex];
                    int left = sqHeap->data[leftIndex];
                    int condition; // 条件
                    if (sqHeap->isBigTopHeap == 1) {
                        condition = (cur < left);
                    } else {
                        condition = (cur > left);
                    }
                    if (condition) {
                        sqHeap->data[curIndex] = left;
                        sqHeap->data[leftIndex] = cur;
                        break;
                    }
                } else {
                    // 有左右子树
                    int cur = sqHeap->data[curIndex];
                    int left = sqHeap->data[leftIndex];
                    int right = sqHeap->data[rightIndex];
                    int max = (left < right ? right : left);
                    int condition; // 条件
                    if (sqHeap->isBigTopHeap == 1) {
                        condition = (cur < max);
                    } else {
                        condition = (cur > max);
                    }
                    if (condition) {
                        if (max == left) {
                            sqHeap->data[curIndex] = left;
                            sqHeap->data[leftIndex] = cur;
                            curIndex = leftIndex;
                            leftIndex = curIndex * 2;
                            rightIndex = leftIndex + 1;
                        } else {
                            sqHeap->data[curIndex] = right;
                            sqHeap->data[rightIndex] = cur;
                            curIndex = rightIndex;
                            leftIndex = curIndex * 2;
                            rightIndex = leftIndex + 1;
                        }
                    } else {
                        // 完成堆化
                        break;
                    }
                }
            }
        } else {
            // 需要从下往上堆化
            while (fatherIndex != 0) {
                int cur = sqHeap->data[curIndex];
                int father = sqHeap->data[fatherIndex];

                int condition; // 条件
                if (sqHeap->isBigTopHeap == 1) {
                    condition = (cur > father);
                } else {
                    condition = (cur < father);
                }
                if (condition) {
                    sqHeap->data[fatherIndex] = cur;
                    sqHeap->data[curIndex] = father;
                    curIndex = fatherIndex;
                    fatherIndex = curIndex / 2;
                } else {
                    break;
                }
            }

        }
        return OK;
    } else {
        printf("没找到\n");
        return ERROR;
    }
}

/* 遍历堆 */
Status SqHeapDisplay(SqHeap *sqHeap) {
    for (int i = 0; i <= sqHeap->index; ++i) {
        printf("%d ",sqHeap->data[i]);
    }
    printf("\n");
}

void displayArray(int a[],int length) {
    printf("数组：");
    for (int i = 0; i < length; ++i) {
        printf("%d ",a[i]);
    }
    printf("\n");
}

/* 堆排序：
 * 今天的内容到此就讲完了。我这里要稍微解释一下，在前面的讲解以及代码中，我都假设，堆中的数据是从数组下标为 1
 * 的位置开始存储。那如果从 0 开始存储，实际上处理思路是没有任何变化的，唯一变化的，可能就是，代码实现的时候，
 * 计算子节点和父节点的下标的公式改变了。如果节点的下标是 i，那左子节点的下标就是 2*i+1，右子节点的下标就是
 * 2*i+2，父节点的下标就是 (i-1)/2。*/
void SqHeapSort(int a[],int length) {
    // 1、堆化
    /* 方式1,从上往下:跟推插入一样:
     * 第一种是借助我们前面讲的，在堆中插入一个元素的思路。尽管数组中包含 n 个数据，但是我们可以假设，
     * 起初堆中只包含一个数据，就是下标为 1 的数据。然后，我们调用前面讲的插入操作，将下标从 2 到 n
     * 的数据依次插入到堆中。这样我们就将包含 n 个数据的数组，组织成了堆。
     * */
    /*
    int i = 2;
    while (i < length) {
        int j = i;
        while (j/2 != 0) {
            if (a[j/2] < a[j]) {
                int tmp = a[j/2];
                a[j/2] = a[j];
                a[j] = tmp;
            }
            j = j/2;
        }
        i++;
    }
    // debug
    for (int j = 0; j < length; ++j) {
        printf("%d ",a[j]);
    }
    printf("\n");
    //*/

    /* 方式2，从下往上堆化
     * 第二种实现思路，跟第一种截然相反，也是我这里要详细讲的。第一种建堆思路的处理过程是从前往后处理数组数据，并
     * 且每个数据插入堆中时，都是从下往上堆化。而第二种实现思路，是从后往前处理数组，并且每个数据都是从上往下堆化。
     * 因为叶子节点往下堆化只能自己跟自己比较，所以我们直接从最后一个非叶子节点开始，依次堆化就行了。
     * 对于完全二叉树来说，下标从 n/2+1 到 n 的节点都是叶子节点。
     * */
    int maxIndex = length - 1;
    for (int i = maxIndex / 2; i >= 1; --i) {
        int j = i;
        while (1) {
            int tmpIndex = j; // 记录最大值的下标
            if (a[j*2] > a[j] && j*2 <= maxIndex) {
                tmpIndex = j*2;
            }
            if (a[j*2+1] > a[tmpIndex] && j*2+1 <= maxIndex) {
                tmpIndex = j*2+1;
            }
            // 因为是从下到上堆化的，所以如果当前这个就是最大值了就不需要堆化了
            if (tmpIndex == j) {
                break;
            }
            int tmp = a[j];
            a[j] = a[tmpIndex];
            a[tmpIndex] = tmp;
            j = tmpIndex;
        }
    }
    // debug
    displayArray(a,length);

    // 1、排序
    /*
     * 建堆结束之后，数组中的数据已经是按照大顶堆的特性来组织的。数组中的第一个元素就是堆顶，
     * 也就是最大的元素。我们把它跟最后一个元素交换，那最大元素就放到了下标为 n 的位置。这
     * 个过程有点类似上面讲的“删除堆顶元素”的操作，当堆顶元素移除之后，我们把下标为 n 的元
     * 素放到堆顶，然后再通过堆化的方法，将剩下的 n−1 个元素重新构建成堆。堆化完成之后，我
     * 们再取堆顶的元素，放到下标是 n−1 的位置，一直重复这个过程，直到最后堆中只剩下标为 1
     * 的一个元素，排序工作就完成了。
     * */
    for (int j = length-1;  j > 1; --j) {
        int tmp = a[1];
        a[1] = a[j];
        a[j] = tmp;
        // 对1到j-1下标的元素重新堆化
        int inner_maxIndex = j-1;
        for (int k = inner_maxIndex / 2; k >= 1; --k) {
            int l = k;
            while (1) {
                int inner_tmpIndex = l;
                if (a[l*2] > a[l] && l*2 <= inner_maxIndex) {
                    inner_tmpIndex = l*2;
                }
                if (a[l*2+1] > a[inner_tmpIndex] && l*2+1 <= inner_maxIndex) {
                    inner_tmpIndex = l*2+1;
                }
                if (inner_tmpIndex == l) {
                    break;
                }
                int tmp = a[l];
                a[l] = a[inner_tmpIndex];
                a[inner_tmpIndex] = tmp;
                l = inner_tmpIndex;
            }
        }
    }
    printf("排序完");
    displayArray(a,length);
}


/* 顺序堆测试demo */
void SqHeapDemo() {

    printf("--------------------------- 顺序堆插入 ------------------------\n");
    SqHeap *sqHeap = SqHeapCreateAndInit(1);
    int a[] = {3,2,7,10,5,4,1,8,9,6};
    int a_length = sizeof(a)/ sizeof(int);
    for (int i = 0; i < a_length; ++i) {
        Status result = SqHeapInsert(sqHeap,a[i]);
        printf("插入结果 : %d\n",result);
        SqHeapDisplay(sqHeap);
    }

    printf("--------------------------- 顺序堆删除 ------------------------\n");
    int b[] = {7,1,6,2,8,3};
//    int b[] = {9};
    int b_length = sizeof(b)/ sizeof(int);
    for (int i = 0; i < b_length; ++i) {
        Status result = SqHeapDelete(sqHeap,b[i]);
        printf("删除%d结果 : %d\n",b[i],result);
        SqHeapDisplay(sqHeap);
    }

    printf("--------------------------- 堆排序 ------------------------\n");
    int c[] = {0,7,5,19,8,4,1,20,13,16};
    int c_length = sizeof(c)/ sizeof(int);
    SqHeapSort(c,c_length);



}